package com.tgy.dynamic.programming;

/**
 * @Author: tgy
 * @Date: 2020/11/11 8:44 下午
 */
public class MaxSubArray {

    public int maxSubArray(int[] array) {

        if (array == null || array.length == 0) {

            return 0;
        }

//        int[] dp = new int[array.length];

//        dp[0] = array[0];

        int dp = array[0];
        int max = dp;
        for (int i = 1; i < array.length; i++) {

            if (dp <= 0) {

                dp = array[i];
            }else {

                dp = dp + array[i];
            }

            if (dp > max) {

                max = dp;
            }
        }

        return max;
    }

}
